'''
https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges/description/
'''
from functools import cache, lru_cache


class Solution:
    def minDays(self, n: int) -> int:
        @cache
        @lru_cache(maxsize=512)
        def f(n):
            if n <= 1:
                return n
            p2 = n % 3 + f(n // 3)
            p1 = n % 2 + f(n // 2)
            return 1 + min(p1, p2)
        return f(n)

    def minDays2(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = 1 + min(i % 3 + dp[i // 3], i % 2 + dp[i // 2])
        return dp[n]

print(Solution().minDays(10))